【数论】乘法逆元

真的我也不知道标题怎么起 $QvQ……$

本文将介绍两种求乘法逆元的方式。

0XFF 乘法逆元是什么？

乘法逆元，一般用于求
$\frac{a}{b} \ \ (mod \ p)$
的值 ($p$ 通常为质数) 。

对于加、减、乘法的取模直接取就好了，但是对于除法(上面的分数形式)取模的话，显然直接取模是错的，那么这个时候就需要用到乘法逆元。

如果 $a \times x \equiv 1 \ \ (mod \ p) $，且 $a$ 与 $p$ 互质，那么就可以定义 $p$ 为 $x$ 的逆元，记为 $a^{-1}$，所以我们也可以称 $x$ 为 $a$ 在 $mod \ p$ 意义下的倒数。

对于 $\frac{a}{b} \ \ (mod \ p)$，这个分数的值就是 $(b^{-1} \times a) \ mod \ p$，即 $b$ 在 $mod \ p$ 意义下的逆元乘上 $a$ ，最后对 $p$ 取模。

0X1F 求乘法逆元的两种方法

(我只会这两种)……

0X1F-1 费马小定理求乘法逆元

费马小定理：

若 $p$ 为质数，$a$ 为正整数，且 $a$ 与 $p$ 互质。

那么 $a^{p-1} \equiv 1 \ \ (mod \ p)$。

我们将 $a^{p-1} \equiv 1 \ \ (mod \ p)$ 代入原式：

$a \times x \equiv 1 \ \ (mod \ p)$ $a \times x\equiv a^{p-1} \ \ (mod \ p)$ $x\equiv a^{p-2} \ \ (mod \ p)$

那么直接跑一遍快速幂即可。

Code:

#define ll long long
ll pow(ll x,ll y,ll p) {
	x%=p;
    ll ans=1;
	for(;y;y>>=1,x=x*x%mod)
		if(power&1)ans=ans*x%mod;
	return ans;
}
int main(){
	ll x=pow(a,p-2,p);
}

0X1F-2 线性求乘法逆元

这个算法的时间复杂度是线性的：$O(n)$

设 $p=s \times i + r$ ，$(1<r<i<p)$.

将此式套入 $(mod \ p)$ 意义下的式子就可以得到：

$s \times i +r \equiv 0 \ \ (mod \ p)$

两边同时乘上 $i^{-1}$：

$s + r \times i^{-1} \equiv 0 \ \ (mod \ p)$

然后再同时乘上 $r^{-1}$：

$s \times r^{-1} + i^{-1} \equiv 0 \ \ (mod \ p)$

移项得到：

$i^{-1} \equiv -s \times r^{-1} \ \ (mod \ p)$

很显然 $s$ 等于 $[\frac{p}{i}]$，$r$ 等于 $p \ mod \ i$，那么 $r^{-1}$ 就等于 $inv[p \ mod \ i]$ ($inv[i]$ 表示 $i$ 在 $mod \ p$ 意义下的乘法逆元)

然后代入公式：

$inv[i] \equiv - [\frac{p}{i}] \times inv[p \ mod \ i] \ \ (mod \ p)$

于是代码就很短了：

1
2
3

inv[0]=0,inv[1]=1;
for(int i=2;i<=n;++i)
	inv[i]=(long long)(p-p/i)*inv[p%i]%p;

一般来说线性的或许会优秀些，建议使用线性的算法，而且代码也比较短，容易写，处理组乘法逆元的时候，第一种的复杂度为 $O(nlogn)$，第二种只需 $O(n)$。但是在处理单组乘法逆元的时候，第一种复杂度为 $O(logn)$，但是第二种因为要讲 $p \ mod \ i$ 求出来，复杂度…..或许还是 $O(n)$。(实际上我也不会证 $QvQ…$)

本文标题:【数论】乘法逆元

文章作者:Qiuly

发布时间:2019年02月20日 - 00:00

最后更新:2019年03月29日 - 13:51

原始链接:http://qiulyblog.github.io/2019/02/20/[数论]乘法逆元/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。